//题目:
// 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。

// 示例 1:
// 输入：heights = [2,1,5,6,2,3]
// 输出：10
// 解释：最大的矩形为图中红色区域，面积为 10

// 示例 2：
// 输入： heights = [2,4]
// 输出： 4

#include<iostream>
#include<vector>
#include<stack>

using namespace std;

//代码:
class Solution 
{
public:
    int largestRectangleArea(vector<int>& heights) 
    {
        //1.暴力解法————O(N^2)————超时辣！
        // int ret=0;
        // for(int i=0;i<heights.size();i++)
        // {
        //     int min_sz=heights[i];
        //     for(int j=i;j<heights.size();j++)
        //     {
        //         min_sz=min(min_sz,heights[j]);
        //         ret=max(ret,(j-i+1)*min_sz);
        //     }
        // }
        // return ret;

        //单调栈————以heights[i]为高度的柱子面积
        vector<int> left(heights.size()),right(heights.size(),heights.size());
        int ret=0;
        stack<int> st;
        for(int i=0;i<heights.size();i++)
        {
            while(!st.empty() && heights[st.top()]>=heights[i])
                st.pop();
            left[i]=st.empty()?-1:st.top();//拿到height[i]左边第一个比它自己小的元素下标
            st.push(i);
        }
        st=stack<int>();
        for(int i=0;i<heights.size();i++)
        {
            while(!st.empty() && heights[i]<heights[st.top()])
            {
                right[st.top()]=i;//拿到height[i]右边第一个比它自己小的元素下标
                st.pop();
            }
            st.push(i);
        }
        for(int i=0;i<heights.size();i++)
            ret=max(ret,heights[i]*(right[i]-left[i]-1));

        return ret;
    }
};